package code701_800.code1_10;

/**
 * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，
 * 写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
 *
 * 输入: nums = [-1,0,3,5,9,12], target = 9
 * 输出: 4
 * 解释: 9 出现在 nums 中并且下标为 4
 *
 * 输入: nums = [-1,0,3,5,9,12], target = 2
 * 输出: -1
 * 解释: 2 不存在 nums 中因此返回 -1
 */
public class _704search {

    /**
     * 大意了，本题是有序数组中找一个元素，明显考的是二分查找，直接便利的话，效率如下。
     * 执行用时：     * 1 ms     * , 在所有 Java 提交中击败了     * 10.66%     * 的用户
     * 内存消耗：     * 39.4 MB     * , 在所有 Java 提交中击败了     * 47.65%     * 的用户
     *
     * @param nums
     * @param target
     * @return
     */
    public int search1(int[] nums, int target) {
        if(nums.length==0)return -1;
        if(nums[0]>target||nums[nums.length-1]<target)return -1;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]==target){
                return i;
            }
        }
        return -1;
    }

    /**
     * 二分实现
     *
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 39.1 MB     * , 在所有 Java 提交中击败了     * 87.78%     * 的用户
     *
     * 总结：二分查找是：移动左指针+1多扩展一位，移动右指针减一多扩展一位。便于找到答案。
     *
     * @param nums
     * @param target
     * @return
     */
    public static int search(int[] nums, int target) {
        if(nums.length==0)return -1;
        if(nums[0]>target||nums[nums.length-1]<target)return -1;
        int left = 0;
        int right = nums.length-1;
        int mid;
        while (left<=right){
            mid = (right+left)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(search(new int[]{-1,0,3,5,9,12},9));
    }

}
